 ///
 /// @file    distance.cc
 /// @author  lemon(haohb13@gmail.com)
 /// @date    2016-03-30 17:27:52
 ///

#include <stdio.h>
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

int tripleMin(const int & a, const int & b, const int & c)
{
	return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int distance(const string & lhs, const string & rhs)
{
	int lhsLen = lhs.size();
	int rhsLen = rhs.size();
	int edit[lhsLen + 1][rhsLen + 1];
	for(int idx = 0; idx <= lhsLen; ++idx)
	{
		edit[idx][0] = idx;
	}
	for(int idx = 0; idx <= rhsLen; ++idx)
	{
		edit[0][idx] = idx;
	}

	for(int i = 0; i < lhsLen; ++i)
	{
		string lhsCh = lhs.substr(i, 1);
		for(int j = 0; j < rhsLen; ++j)
		{
			string rhsCh = rhs.substr(j, 1);
			if(lhsCh == rhsCh)
			{
				edit[i+1][j+1] = edit[i][j];
			}
			else
			{
				edit[i+1][j+1] = tripleMin(
					edit[i][j] + 1,
					edit[i][j+1] + 1,
					edit[i+1][j] + 1);
			}
		}
	}
	return edit[lhsLen][rhsLen];
}


int main(void)
{
	string s1 = "xhello";
	string s2 = "ello";

	cout << "distance = " << ::distance(s1, s2) << endl;
}
